package hacker_rank._101hackfeb;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collection;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;

public class CountLuck {

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int T = Integer.parseInt(br.readLine());

		for (int t = 0; t < T; t++) {
			String[] line = br.readLine().split(" ");
			int N = Integer.parseInt(line[0]);
			int M = Integer.parseInt(line[1]);

			String[] grid = new String[N];

			int her_r = 0, her_c = 0, exit_r = 0, exit_c = 0;
			for (int i = 0; i < N; i++) {
				grid[i] = br.readLine();
				if (grid[i].indexOf('M') != -1) {
					her_r = i;
					her_c = grid[i].indexOf('M');
				}
				if (grid[i].indexOf('*') != -1) {
					exit_r = i;
					exit_c = grid[i].indexOf('*');
				}
			}

			int K = Integer.parseInt(br.readLine());

			// solve(grid, her_c, her_c, exit_r, exit_c, K);
			bfs(N, M, K, her_r, her_c, exit_r, exit_c, grid);

		}

	}

	private static void bfs(int r, int c, int K, int her_r, int her_c,
			int exit_r, int exit_c, String[] grid) {

		Queue<Node> q = new LinkedList<Node>();

		Node start = new Node(her_r, her_c);
		q.add(start);

		while (!q.isEmpty()) {
			Node cu = q.remove();
			if (cu.x == exit_r && cu.y == exit_c)
				break;

			for (Node n : getAdjacentNodes(grid, r, c, cu)) {
				q.add(n);
			}
		}
	}

	static Collection<Node> getAdjacentNodes(String[] grid, int r, int c,
			Node cu) {
		List<Node> li = new ArrayList<Node>();

		cu.visited = true;
		NodeFactory.update(cu);

		int ch = 0;
		if (cu.x - 1 >= 0 && grid[cu.x - 1].charAt(cu.y) != 'X'
				&& !NodeFactory.getNode(cu.x - 1, cu.y).isVisited())
			ch++;

		// LEFT
		if (cu.y - 1 >= 0 && grid[cu.x].charAt(cu.y - 1) != 'X'
				&& NodeFactory.getNode(cu.x, cu.y - 1).isVisited() == false)
			ch++;

		// RIGHT
		if (cu.y + 1 < c && grid[cu.x].charAt(cu.y + 1) != 'X'
				&& NodeFactory.getNode(cu.x, cu.y + 1).isVisited() == false)
			ch++;

		// DOWN
		if (cu.x + 1 < r && grid[cu.x + 1].charAt(cu.y) != 'X'
				&& NodeFactory.getNode(cu.x + 1, cu.y).isVisited() == false)
			ch++;

		System.out.println("ch: " + ch);
		// ********************************

		// UP
		if (cu.x - 1 >= 0 && grid[cu.x - 1].charAt(cu.y) != 'X'
				&& NodeFactory.getNode(cu.x - 1, cu.y).isVisited() == false) {
			Node t = NodeFactory.getNode(cu.x - 1, cu.y);
			if (ch > 1) {
				t.waves++;
			} else {
				t.waves = cu.waves;
			}
			NodeFactory.update(t);

			li.add(NodeFactory.getNode(cu.x - 1, cu.y));

		}

		// LEFT
		if (cu.y - 1 >= 0 && grid[cu.x].charAt(cu.y - 1) != 'X'
				&& !NodeFactory.getNode(cu.x, cu.y - 1).isVisited()) {
			Node t = NodeFactory.getNode(cu.x, cu.y - 1);
			if (ch > 1) {
				t.waves++;
			} else {
				t.waves = cu.waves;
			}
			NodeFactory.update(t);
			li.add(NodeFactory.getNode(cu.x, cu.y - 1));

		}

		// RIGHT
		if (cu.y + 1 < c && grid[cu.x].charAt(cu.y + 1) != 'X'
				&& !NodeFactory.getNode(cu.x, cu.y + 1).isVisited()) {
			Node t = NodeFactory.getNode(cu.x, cu.y + 1);
			if (ch > 1) {
				t.waves++;
			} else {
				t.waves = cu.waves;
			}
			NodeFactory.update(t);
			li.add(NodeFactory.getNode(cu.x, cu.y + 1));
		}

		// DOWN
		if (cu.x + 1 < r && grid[cu.x + 1].charAt(cu.y) != 'X') {
			Node t = NodeFactory.getNode(cu.x + 1, cu.y);
			if (ch > 1) {
				t.waves++;
			} else {
				t.waves = cu.waves;
			}
			NodeFactory.update(t);

			li.add(NodeFactory.getNode(cu.x + 1, cu.y));

		}

		return li;
	}

	static class Result {
		public int res;

		public Result() {
			this.res = 0;
		}
	}

	public static class Node {
		public int x;
		public int y;
		public boolean visited;
		public int waves;

		public Node(int x, int y) {
			this.x = x;
			this.y = y;
			this.visited = false;
			this.waves = 0;
		}

		public boolean isVisited() {
			return this.visited;
		}

		@Override
		public boolean equals(Object obj) {
			if (obj instanceof Node == false) {
				return false;
			}
			Node t = (Node) obj;
			if (this.x == t.x && this.y == t.y)
				return true;
			else
				return false;
		}

		@Override
		public int hashCode() {
			return (this.x * 13 * 13) + (this.y * 13);
		}

	}

	static class NodeFactory {
		private static Map<Integer, Node> createdNodes = new HashMap<Integer, Node>();

		public static Node getNode(int x, int y) {
			Node t = createdNodes.get(hash(x, y));
			if (t == null) {
				t = new Node(x, y);
				createdNodes.put(hash(x, y), t);
			}
			return t;
		}

		public static void update(Node t) {
			createdNodes.put(hash(t.x, t.y), t);
		}

		static int hash(int x, int y) {
			return x * 13 * 13 + y * 13;
		}

	}

}
